﻿using System;
using System.Collections.Generic;

namespace h87
{
    public class Solution {
        public int MaxEnvelopes(int[][] envelopes) {
            if(envelopes.Length == 0)
                return 0;

            Array.Sort(envelopes, new IntComparer());
        
            int max = 1;
        
            int[] dp = new int[envelopes.Length];
            for(int i = 0; i < dp.Length; i ++){
                dp[i] = 1;
            }
        
            //一维最长公共子序列问题 比的是信封高度
            for(int i = 1; i < dp.Length; i ++){
                for(int j = 0; j < i; j ++){
                    if(envelopes[j][1] < envelopes[i][1]){
                        dp[i] = Math.Max(dp[i], dp[j] + 1);
                    }
                }
                max = Math.Max(max, dp[i]);
            }
            return max;
        }
    }
//重写Array.Sort比较器 en数组的每一项都是一个长度为2的int数组 所以这里泛型为int[]
    public class IntComparer : IComparer<int[]>{
        public int Compare(int[] arr1, int[] arr2) {
            // 按宽度升序排列，如果宽度⼀样，则按⾼度降序排列，避免相同宽度的错误情况
            if (arr1[0] == arr2[0]) {
                return arr2[1] - arr1[1];
            } else {
                return arr1[0] - arr2[0];
            }
        }
    }


}